def max_heapify(heap, index=0, length=nil)
    if length.nil?
        length = heap.length
    end
    left = index * 2 + 1
    right = left + 1
    largest = index
    if (left <= (length - 1)) and (heap[left] > heap[largest])
        largest = left
    end
    if (right <= (length - 1)) and (heap[right] > heap[largest])
        largest = right
    end
    if largest != index
        heap[index], heap[largest] = heap[largest], heap[index]
        max_heapify(heap, largest, length)
    end
end


def build_heap(to_sort)
    (to_sort.length / 2).downto(0) do |index|
        max_heapify(to_sort, index)
    end
end


def heapsort(heap)
    build_heap(heap)
    (heap.length - 1).downto(1) do |index|
        heap[0], heap[index] = heap[index], heap[0]
        max_heapify(heap, 0, index)
    end
end


if __FILE__ == $0
    heap = Array.new(ARGV.length){|index| ARGV[index].to_i}
    heapsort(heap)
    print '['
    print heap.join(', ')
    puts ']'
end
